package com.jhxy.algorithm.merge;

import com.jhxy.algorithm.util.InputsForMerge;
import com.jhxy.algorithm.util.PrintTool;

import java.util.List;

/**
 * 合并两个有序数组:顺序归并
 * 用空间换时间
 */
public class MergeOrder {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //代表nums1数组的角标
        int i = 0;
        //代表nums2数组的角标
        int j = 0;
        //排序的数组
        int[] sorted = new int[m + n];
        //排序好的数组的角标
        int sortedIndex = 0;

        while (i < m && j < n) {
            if (nums1[i] >= nums2[j]) {
                sorted[sortedIndex] = nums2[j];
                sortedIndex++;
                j++;
            } else {
                sorted[sortedIndex] = nums1[i];
                sortedIndex++;
                i++;
            }
        }

        //当出现一个数组已经把所有的数全部放到的sorted中后，另外一个数组还有没有放完的数据
        if (i == m) {
            //说明nums2数组还有数据没有放完
            while (j < n) {
                sorted[sortedIndex] = nums2[j];
                sortedIndex++;
                j++;
            }
        } else if (j == n) {
            //说明nums2数组的所有数据已经全部移到sorted中了
            while (i < m) {
                sorted[sortedIndex] = nums1[i];
                sortedIndex++;
                i++;
            }
        }

        //赋值sorted到nums1中
        for (int k = 0; k < m + n; k++) {
            nums1[k] = sorted[k];
        }

    }

    public static void main(String[] args) {
        InputsForMerge inputs = new InputsForMerge("1,2,3,0,0,0;0;1", "3;0;1", "2,5,6;1;0", "3;1;0");
        PrintTool print = new PrintTool();
        MergeOrder ins = new MergeOrder();
        int i = 1;
        for (List<Object> input : inputs.inputs) {
            System.out.println("=================第" + (i++) + "组输入输出=================");
            print.printArray((int[]) input.get(0));
            System.out.println("");
            System.out.println("m:" + (int) input.get(1));
            print.printArray((int[]) input.get(2));
            System.out.println("");
            System.out.println("n:" + (int) input.get(3));
            int[] nums1 = (int[]) input.get(0);
            ins.merge(nums1, (int) input.get(1), (int[]) input.get(2), (int) input.get(3));
            print.printArray(nums1);
            System.out.println("");
        }
    }
}
